package com.melo;

import org.apache.commons.lang.StringUtils;

import java.util.*;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 贪心算法实现类
 * @date 2025-05-08
 */
public class Greedy {

    public static List<String> greedy(Map<String, Set<String>> broadcastMap, Set<String> areaSet) {
        // 已选择的电台
        List<String> selectedList = new ArrayList<>();

        // 遍历过程中, 当前处理电台覆盖的地区和还没有覆盖到地区的交集
        Set<String> tempAreaIntersectionSet = new HashSet<>();
        // 遍历过程中, 能够覆盖最大未覆盖的地区对应的电台的key
        String tempMostMatchedBroadcastName = StringUtils.EMPTY;
        // 遍历过程中, 能够覆盖最大未覆盖的地区对应的电台的key
        Set<String> tempNonMatchedBroadcastNameSet = new HashSet<>();

        while (!areaSet.isEmpty()) {
            for (String broadcastName : broadcastMap.keySet()) {
                Set<String> broadcastAreaSet = broadcastMap.get(broadcastName);

                tempAreaIntersectionSet.addAll(broadcastAreaSet);
                // 求tempAreaIntersectionSet和areaSet的交集, 并把交集赋给tempAreaIntersectionSet
                tempAreaIntersectionSet.retainAll(areaSet);

                if (tempAreaIntersectionSet.isEmpty()) {
                    // 当前电台覆盖不到剩余地区
                    tempNonMatchedBroadcastNameSet.add(broadcastName);
                    continue;
                }

                // 当前电台还存在没有覆盖到的地区; 当前电台覆盖的地区比mostMatchedBroadcastName覆盖的地区还多【贪心算法】
                if ((StringUtils.isEmpty(tempMostMatchedBroadcastName) || tempAreaIntersectionSet.size() > broadcastMap.get(broadcastName).size())) {
                    tempMostMatchedBroadcastName = broadcastName;
                }

                tempAreaIntersectionSet.clear();
            }

            if (StringUtils.isNotEmpty(tempMostMatchedBroadcastName)) {
                selectedList.add(tempMostMatchedBroadcastName);
                // 将当前电台覆盖的区域从区域集合中删除
                areaSet.removeAll(broadcastMap.get(tempMostMatchedBroadcastName));
                // 将当前电台从电台集合中删除
                broadcastMap.remove(tempMostMatchedBroadcastName);
                if (!tempNonMatchedBroadcastNameSet.isEmpty()) {
                    // 将无用的电台从电台集合中删除
                    tempNonMatchedBroadcastNameSet.forEach(broadcastMap::remove);

                    tempNonMatchedBroadcastNameSet.clear();
                }

                // 重置临时变量
                tempMostMatchedBroadcastName = StringUtils.EMPTY;
            }
        }

        return selectedList;
    }
}
